<?php
/**
 * 改进过的不相交集类
 */
class FastDisjointSets extends DisjointSets
{
    /**
     * 返回元素所在的集合
     * 使用路径压缩
     * @param int $index
     */
    public function find($index)
    {
        if($this->list[$index]<0){
            return $index;
        }
        else{
            return $this->list[$index]=$this->find($this->list[$index]);
        }
    }
    /**
     * 合并两个原来不相交的集合
     * 使用高度(秩)进行灵巧求并，根节点的值是相交节点的树的高度的负数
     * @param int $index1
     * @param int $index2
     */
    // public function union($index1, $index2)
    // {
    //     $root1=$this->find($index1);
    //     $root2=$this->find($index2);
    //     if($this->list[$root2] < $this->list[$root1]){
    //         $this->list[$root1] = $root2;
    //     }
    //     else{
    //         if($this->list[$root2] === $this->list[$root1]){
    //             $this->list[$root1]--;
    //         }
    //         $this->list[$root2] = $root1;
    //     }
    // }
    /**
     * 合并两个原来不相交的集合
     * 使用大小进行灵巧求并，根节点的值是所有相交节点的总数的负数
     * @param int $index1
     * @param int $index2
     */
    public function union($index1, $index2)
    {
        $root1=$this->find($index1);
        $root2=$this->find($index2);
        if($this->list[$root2] < $this->list[$root1]){
            $this->list[$root2] += $this->list[$root1];
            $this->list[$root1] = $root2;
            return $this->list[$root2];
        }
        else{
            $this->list[$root1] += $this->list[$root2];
            $this->list[$root2] = $root1;
            return $this->list[$root1];
        }
    }
}
